package easy;

import java.util.*;

/**
 * Created by daodao on 2017/11/30.
 * Problem 20
 * Description: Given a string containing just the characters '(', ')', '{', '}', '[' and ']',
 * determine if the input string is valid.The brackets must close in the correct order,
 * "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
 */
public class ValidParentheses {
    public static boolean isValid(String s) {
        if ("".equals(s)) return true;
        if (s.length() % 2 != 0) return false;
        Stack<Character> stack = new Stack<Character>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else if (stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}
